#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
#include "stack"
using namespace std;

/*HJJ QQ479287006
 *剑指 Offer 68 - II. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]
 * */

/*
 * 递归方式
 * 出口 如果 root==p 或者root==q 返回root root==null 返回root
 *
 *  重复 lef =lowestCommonAncestor（lef,p,q）;
 *      right= lowestCommonAncestor（right,p,q）;
 *
 *      lef==null 说明都再右子树上 retrun right
 *      righ==null 都再左子树上  retrun lef
 *
 *
 * 返回值是 他们的 父节点
 *
 *
 * **/
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    if (root == nullptr || root == p || root == q)
        return root;

    TreeNode *left = lowestCommonAncestor(root->left, p, q);

    TreeNode *right = lowestCommonAncestor(root->right, p, q);

    //todo 这边可能难想到
    //如果左右都不为空 返回他们的根 因为刚好出栈 到他们父节点的函数
    if (left && right)
        return root;
    //左边为空 说明在 右边
    if (!left)
        return right;

    if (!right)
        return left;
    //否则返回null
    return nullptr;
}


//非递归方式
//todo 先求根到qp的路径 ， 然后倒叙寻找他们的pq 公共节点。
//获取路径并且逆转
vector<TreeNode *> retTemp;
//获取路径并且逆转
void getPath(TreeNode *root, TreeNode *ptr, vector<TreeNode *> &ret) {
    if (root == nullptr)
        return;
    retTemp.push_back(root);
    if (root == ptr) {
        reverse(retTemp.begin(), retTemp.end());
        ret = retTemp;
        return;
    }
    getPath(root->left, ptr, ret);
    getPath(root->right, ptr, ret);
    retTemp.pop_back();//注意这里的pop 因为那边不是统一收集的 这边又传来了一个临时变量 否则ret的时候 这个数组Wienull了
}

TreeNode *lowestCommonAncestor1(TreeNode *root, TreeNode *p, TreeNode *q) {
    vector<TreeNode *> ps;
    getPath(root, p, ps);
    retTemp.clear();//这里需要清除 因为是公用全局
    vector<TreeNode *> qs;
    getPath(root, q, qs);
    for (const auto &item : ps) {
        auto iter = find(qs.begin(), qs.end(), item);
        if (iter != qs.end()) {
            return *iter;
        }
    }
    return nullptr;
}

//也可以这样 判断最后一个元素是不是那个节点否则就pop 这样也不用开辟数组 。。。。todo
//void getPath(TreeNode root,TreeNode node,List<TreeNode> path){
//    if(root==null)
//        return ;
//    path.add(root);
//    if(root == node)
//        return ;
//    if(path.get(path.size()-1)!=node){
//        getPath(root.left,node,path);
//    }
//    if(path.get(path.size()-1)!=node){
//        getPath(root.right,node,path);
//    }
//    if(path.get(path.size()-1)!=node){
//        path.remove(path.size()-1);
//    }
//}